05 蒙特卡洛方法

MC Basic

基础的蒙特卡洛方法，就是将策略迭代转化为model-free。

在策略迭代中，有PE、PI两步。在PI中，需要求出 $q_{\pi_k}$ ，通过 $q_{\pi_k}$ 来更新策略。而求 $q$ 的公式是与模型有关的。

蒙特卡洛方法使用 $q_{\pi_k}$ 的原始定义。

q_{\pi_k}(s, a) = E[G_t|S_t = s, A_t = a]

所以，在模型的具体数据分布不确定时，需要大量的样本（经验）。对于状态 $(s,a)$ ，采取若干次 $\pi_k$ 策略，会得到若干回报 $g(s,a)$ ，则

q_{\pi_k}(s, a) = E[G_t|S_t = s, A_t = a] \approx \Sigma^N_{i=1}g^{(i)}(s,a) / N

MC Basic的具体步骤如下：

猜测策略 $\pi_0$
迭代
- PE
  - 对所有 $(s,a)$ ，基于现有策略进行数次尝试
  - 计算回报均值，得到 $q_{\pi_k}(s,a)$
- PI
  - 与策略迭代相同，更新策略

在每个episode中，理论上走无限步才能得到最准确的 $q$ 。需要人为设置episode length，在一定步数后停止。直观上，可以将episode length理解为模型探索的半径。episode length需要达到一定值，离出发点较远的状态价值才能被更新，也就是说episode length需要充分长，让模型能探索到最优解；但是不必无限增长。

MC Exploring Starts

MC Basic本身的效率较低，可以进一步推广。

首先，在MC Basic中每次尝试都只能更新最开始那个点；可以对episode中每个 $(s,t)$ 都计算对应的回报，求平均来得到最终的回报。对于这种优化，又有两种不同策略。

first-visit method：如果某个 $(s,t)$ 在同一episode中出现不止一次，则只有第一次（距终点最远时）更新
every-visit method：每次更新

MC Exploring Starts采用first-visit method。

此外，原有的算法中，必须某个episode结束后才可以进行更新。在MC Exploring Starts中，在episode的每一步都可以进行更新，采用了GPI的思想。

具体步骤如下：

猜测策略 $\pi_0$
对于每次尝试
- 生成episode
- 初始化 $g$ 为0
- 对于episode的每一步，从 $T - 1$ $T - 1$ 遍历到0
  - $g = \gamma g + r_{t + 1}$
  - 如果 $(s_t, a_t)$ $(s_{t}, a_{t})$ 未在当前episode中出现
    - $Returns(s_t, a_t) = Returns(s_t, a_t) + g$
    - $q(s_t, a_t) = average(Returns(s_t, a_t))$
    - 如果新 $q$ 是最大的，更新 $\pi(a|s_t)$

这种算法要求每个 $(s,a)$ 都要作为起点一次，在实际中可能很难做到。

MC Epsilon-Greedy Policy

$\epsilon$ -greedy policy是一种soft policy。

令 $\epsilon \in [0,1]$ ， $|A(s)|$ 是状态 $s$ 下可采取的action数量，令

\pi(a|s) = \begin{cases} 1 - \dfrac{\epsilon}{|A(s)|}(|A(s)| - 1),~~for~the~greedy~action \\ \dfrac{\epsilon}{|A(s)|},~~for~the~other~actions \end{cases}

这种情况下，每个action都有概率被选到，同时也保证了最好的action有最大的被选择概率。这种算法平衡了exploitation（充分利用）和exploring（探索）。

具体步骤：

猜测策略 $\pi_0$
对于每次尝试
- 生成episode
- 初始化 $g$ 为0
- 对于episode的每一步，从 $T - 1$ $T - 1$ 遍历到0
  - $g = \gamma g + r_{t + 1}$
  - $Returns(s_t, a_t) = Returns(s_t, a_t) + g$
  - $q(s_t, a_t) = average(Returns(s_t, a_t))$
  - 如果新 $q$ 是最大的，更新 $\pi(a|s_t)$

在这种情况下，可以使用every-visit，减少episode的数量。由于这种策略具有随机性，整个回合都在进行探索，无法获得“纯净的”、从某个 $(s,a)$ 开始的样本；此外，生成完整回合成本很高。理论上， $\epsilon$ -greedy的估计方法是有偏的，但是在实践中被证明收敛得很好，且带来的效率提升超过了理论的偏差问题。

05 蒙特卡洛方法